The invention relates to packet-based computer networks, and more particularly to controlling traffic rates within a packet-based network.
Packet-based networks are known to transmit data in bursts. Bursty traffic can cause congestion in the network and can cause packets to be dropped when input buffers are full. In order to improve the performance of a network and to provide guaranteed quality of service (QoS), it is necessary to be able to control the flow of traffic at various locations in the network to a particular desired rate. Two techniques for controlling the flow of traffic are generally referred to as rate shaping and rate limiting. Rate shaping involves buffering packets as they arrive at a location and then controlling the flow of packets leaving the buffers according to a given algorithm to meet a desired rate. Because packets are buffered, bursts of packets can be absorbed and then dispatched in a controlled manner such that incoming packets are not dropped. Rate limiting involves measuring the rate of packets coming into a location and then dropping the packets that arrive in excess of the desired rate.
Some common algorithms that can be used to accomplish rate shaping or rate limiting include the well-known leaky bucket and token bucket algorithms. Using a leaky bucket algorithm to accomplish rate shaping involves buffering incoming packets and then dispatching the packets from the buffer at a constant rate, i.e., the leak rate (measured, for example, in bytes/second). For example, when a packet of size C (i.e., in bytes) is received, it is held in the buffer for a time period of C/leak rate before it is dispatched from the buffer. While the buffer is empty, the transmission capacity, as dictated by the leak rate, goes unused and is not accumulated for subsequent bursts of packets. Therefore, when a new burst of packets arrives in the buffer after a period of no traffic, the new packets are still buffered and dispatched at the leak rate. This technique does not provide flexibility to account for the bursty nature of packet-based network traffic.
Using a token bucket algorithm for rate shaping involves assigning a bit value (i.e., 1,000 bytes, 50 cells, etc.) to a bucket at a constant rate and allowing packets to be dispatched from a buffer only if the requisite number of bits, bytes, or cells have accumulated in the bucket. During periods of no traffic, bits continue to accumulate in the bucket at the constant rate and subsequent bursts of traffic can utilize the accumulated bits. Although this technique does provide flexibility to account for the bursty nature of network traffic, if the bucket accumulates too many bits during periods of no traffic, subsequent packet bursts may not be shaped. The size of an allowable burst can be limited by setting a maximum value for the number of bits that can accumulate in a bucket, however the maximum value for the bucket must be at least as large as the largest expected packet in order to prevent a large packet from being trapped in the buffer. A disadvantage to setting the maximum bucket size to the size of the largest expected packet is that it will allow large bursts of relatively small packets to go out unshaped.
Another algorithm that can be used for rate shaping or rate limiting involves calculating a current traffic rate at a location and comparing the current rate to the desired rate to determine whether or not subsequent packets should be dispatched. According to the algorithm, if the current rate is less than the desired rate, then packets are allowed to flow and if the current rate is greater than the desired rate, then packets are not allowed to flow. One known algorithm such as this that is used for rate shaping is referred to as an exponential weighted moving average (EWMA) algorithm. An example of an EWMA algorithm is expressed as:
Current_RateN=(1xe2x88x92Gain)xc2x7Current_RateNxe2x88x921+Gainxc2x7BytesN
with, tN+1=tN+xcex94t
where Current_RateN is the EWMA in the Nth sampling interval, Current_RateNxe2x88x921 is the EWMA in the Nxe2x88x921 sampling interval, and BytesN is the number of bytes that were dispatched during the Nth sampling interval, where each sampling interval has a period of xcex94t. The Gain controls the time constant (i.e., frequency response) of what is essentially a low-pass filter operation. When used to dispatch packets from a buffer, if the Current_RateN is greater than a pre-defined desired rate (referred to as Desired_Rate), then no packets are dispatched. If the Current_RateN is less than the Desired_Rate, then packets are dispatched. An algorithm for controlling the dispatch of packets from a buffer is expressed in the prior art as:
if (Current_RateN greater than Desired_Rate)
No packets dispatched else
Packets dispatched
FIG. 1 depicts an example graph of the current rate of traffic 104 versus time (in increments of xcex94t) that results from application of the above-described EWMA algorithm in a rate shaping system where the buffer is fully loaded with packets. At an initial time, t0, a burst of traffic is dispatched and the current rate, calculated as the EWMA, jumps up above the desired rate, where the desired rate is indicated by horizontal dashed line 106. As long as the current rate is above the desired rate, no new traffic is dispatched and the current rate steadily declines. Once the current rate declines to below the desired rate (i.e., time t2), a new burst of traffic is dispatched and the current rate jumps back up above the desired rate. As depicted in FIG. 1, in a fully loaded system, the current rate of traffic is almost entirely above the desired rate because the moment the current rate drops below the desired rate, more packets are dispatched. Because the current rate is almost entirely above the desired rate, the achieved transmission rate over a period of full loading will be greater than the desired rate, where the achieved rate is calculated as the total number of bits dispatched divided by the time period over which the bits were dispatched. For example, in FIG. 1 the achieved rate 108 over the time period t0 through t9 in a fully loaded system is above the desired rate. Ideally, the achieved rate should be equal to the desired rate.
In view of the need to be able to control certain network traffic to desired rates and in view of the disadvantages of prior art rate shaping and rate limiting algorithms, what is needed is an algorithm that can effectively control packet-based traffic rates, that is flexible, and that is easy to implement, especially in hardware.
A method and system for controlling the flow of packet-based traffic to meet a desired rate involves calculating, as a moving average, a current rate of packet-based traffic on a link, calculating the sum of the error between the calculated current rate and the desired rate, and determining whether or not packets can flow in response to the calculated sum of the error. In an embodiment, when the sum of the error between the current rate and the desired rate is less than or equal to zero, packets are dispatched from a buffer onto a link and when the sum of the error is greater than zero, packets are held in the buffer. Because the flow of packets is controlled in response to the sum of the error between the current rate and the desired rate, the achieved rate of traffic is maintained close to the desired rate even in bursty traffic environments.
In an embodiment of the invention, the sum of the error is compared to a threshold value to determine whether or not packets are allowed to flow. Packets are allowed to flow if the sum of the error is below the threshold and are not allowed to flow if the sum of the error is above the threshold. In an embodiment, the threshold value is zero and packets are allowed to flow if the sum of the error is less than or equal to zero. In another embodiment, packets are allowed to flow when the sum of the error indicates that the achieved rate of traffic is below the desired rate and are not allowed to flow when the sum of the error indicates that the achieved rate of traffic is above the desired rate.
In order to control the magnitude of bursts that are allowed to flow after periods of no traffic, a minimum value can be established for the current rate. The calculated current rate is adjusted to the minimum value if the current rate is below the minimum value. Similarly, a minimum value can be established for the sum of the error, with the calculated sum of the error being adjusted to the minimum value if the sum of the error is below the minimum value. Both of these techniques control the amount of bandwidth that can be xe2x80x9cborrowedxe2x80x9d from periods of silence. Specifically, the later (second) technique prevents large negative residues from accumulating.
In an embodiment, the process of calculating the current rate and the sum of the error and determining whether or not packets can flow is repeated every cycle, wherein a cycle occurs every xcex94t.
In an embodiment, the current rate is calculated as:
Current_Rate=Previous_Rate+(Waxc2x7Cxe2x88x92Wbxc2x7Previous_Rate),
where C represents the number of bits dispatched in the current cycle and where Wa and Wb are weights. When using the above-provided expression, the Previous_Rate for the next calculation cycle can be set to the Current_Rate that was calculated in the last calculation cycle. In an embodiment, Wa is a function of Nc and xcex94t, where xcex94t is a sampling interval and Nc is a constant number of the sampling intervals. More specifically, Wa can be defined as Wa=1/(Ncxc2x7xcex94t). In an embodiment, Wb is a function of Nc. More specifically, Wb can be defined as Wb=1/Nc.
When using the above-provided rate expression, the magnitude of traffic bursts can be controlled by establishing an Initial_Rate and adjusting the Current_Rate to the Initial_Rate if the Current_Rate falls below the Initial_Rate.
The sum of the error can be calculated as:
Current_Error=Previous_Error+(Current_Ratexe2x88x92Desired_Rate),
where the Current_Rate is calculated according to the above-provided expression. The magnitude of packet bursts can be controlled by establishing a minimum threshold for the Current_Error and adjusting the Current_Error to the threshold if the Current_Error falls below the threshold. When using the above-provided error expression, the Previous_Error for the next calculation cycle is set to the Current_Error that was calculated in the last calculation cycle. In an embodiment, packets are allowed to flow if the Current_Error is less than or equal to zero and are not allowed to flow if the Current_Error is greater than zero. The invention can be embodied in a method and system for controlling the flow of packet-based traffic. The method and system can be used for rate shaping or rate limiting and the performance characteristics of the algorithm can be easily adjusted by adjusting the user provided input parameters of Initial_Rate, Desired_Rate, Nc, and xcex94t.
The invention is also embodied in a method that is specific to rate shaping, wherein packets are dispatched from a buffer in response to the calculated sum of the error between the calculated current rate and the desired rate.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.